'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-04 09:22:15
'''
#
# @lc app=leetcode.cn id=57 lang=python3
#
# [57] 插入区间
#

# @lc code=start
from typing import List
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        ans = []
        # from sys import maxsize
        import copy
        add = copy.copy(newInterval)
        for interval in intervals:
            if interval[1]<newInterval[0]:
                ans.append(interval)
            elif interval[0]>newInterval[1]:
                ans.append(interval)
            else:
                add[0], add[1] = min(add[0], interval[0]), max(add[1], interval[1])
        i = 0
        # print(add)
        while i<len(ans):
            if ans[i][1]>add[0]:
                break
            i+=1
        ans = ans[:i]+[add]+ans[i:]
        return ans

# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
    newInterval = [4,8]
    print(solution.insert(intervals, newInterval))